package com.learn.algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class LCR114 {

    public String alienOrder(String[] words) {
        int N = 26;
        // 存储入度
        int[] indegree = new int[N];
        Arrays.fill(indegree, -1); // -1 用于区分没有出现的字母
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                indegree[word.charAt(i) - 'a'] = 0; // 出现过的字母的入度初始化为0
            }
        }
        // 初始化邻接表图
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0, j, len; i < words.length - 1; i++) {
            String current = words[i];
            String next = words[i + 1];
            j = 0;
            len = Math.min(current.length(), next.length());
            for (; j < len; j++) {
                // 第一个出现不同的时候 也就是有顺序了 将其加到邻接表图中
                if (current.charAt(j) != next.charAt(j)) {
                    graph.get(current.charAt(j) - 'a').add(next.charAt(j) - 'a');
                    indegree[next.charAt(j) - 'a']++; // 入度加1
                    break;
                }
            }
            // 前缀都相同 但前一个单词比后一个单词更长 说明给的是个错误的顺序
            if (j < current.length() && j == next.length()) {
                return "";
            }
        }
        int[] queue = new int[N];
        int l = 0, r = 0, kinds = 0;
        for (int i = 0; i < N; i++) {
            if (indegree[i] != -1) {
                kinds++;
            }
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }
        StringBuilder builder = new StringBuilder();
        while (l < r) {
            int cur = queue[l++];
            builder.append((char) (cur + 'a'));
            for (int next : graph.get(cur)) {
                // cur节点的邻居的入度都 -1 任何一个入度为0的邻居 加到队列中
                if (--indegree[next] == 0) {
                    queue[r++] = next;
                }
            }
        }
        return builder.length() == kinds ? builder.toString() : "";
    }

    public static void main(String[] args) {
        LCR114 lcr114 = new LCR114();
        System.out.println(lcr114.alienOrder(new String[]{"wrt", "wrf", "er", "ett", "rftt"}));
    }
}
